package com.niuke;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-10 11:51:03
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-10     张李鑫                     1.0         1.0 Version
 */
public class JZ57 {
    /**
     * 输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，
     * 如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
     */


    /**
     * hash
     *
     * @param array
     * @param sum
     * @return
     */
    public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> integers = new ArrayList<>();
        Set<Integer> map = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            map.add(array[i]);
        }
        for (int i : array) {
            if (map.contains(sum - i)) {
                integers.add(i);
                integers.add(sum - i);
                return integers;
            }

        }
        return integers;
    }

    /**
     * 双指针
     *
     * @param array
     * @param sum
     * @return
     */
    public static ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
        ArrayList<Integer> integers = new ArrayList<>();
        int l = 0;
        int r = array.length - 1;

        while (l < r) {
            if (array[l] + array[r] == sum) {
                integers.add(array[l]);
                integers.add(array[r]);
                break;
            } else if (array[l] + array[r] > sum) {
                r--;
            } else {
                l++;
            }
        }
        return integers;
    }


    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 7, 11, 15};
        System.out.println(FindNumbersWithSum1(arr, 15));
    }
}
